public class KMP 
{
private static void printar(int[] array, int size)
 {
for (int k=0; k<size; k++) {System.out.print(array[k]+" ");}
System.out.println();
}

public static void main(String[] args) {



boolean traceon = true;

String s, p;
int sl,pl;
s = "aabacaabaabaa";
p = "aabaa";
sl = s.length();
pl = p.length();
System.out.println("\nThe given subject string s of " + sl +" elements is:\n " + s);
System.out.println("\nThe given pattern p of "+pl+" elements is:\n "+ p);

int [] pi = new int [pl];
int i, j;
pi[0]=0;
j=0;
for (i=1; i<pl; i=i+1) {
while (j>0 && p.charAt(j)!=p.charAt(i)) {j=pi[j-1];};
if (p.charAt(j)==p.charAt(i)) {j=j+1;};
pi[i]=j;
};
//-------------------------------------------------------------------------
System.out.print("\nThe pi array of " + pl + " elements is:\n ");
printar(pi,pl); System.out.println();
//-------------------------------------------------------------------------
j=0;
for (i=0; i<sl; i=i+1) {
while (j>0 && p.charAt(j)!=s.charAt(i)) {j=pi[j-1];};
if (p.charAt(j)==s.charAt(i)) {j=j+1;};
if (traceon) {System.out.println(" i="+i+" j="+j);}; // tracing
if (j==pl) {
System.out.println("The pattern occurs at position "+(i-pl+1)+"\n");
j=pi[j-1];
};
}; // end of for
}
// end of main
}

/***********************************OUTPUT**************************************
The given subject string s of 13 elements is:
 aabacaabaabaa

The given pattern p of 5 elements is:
 aabaa

The pi array of 5 elements is:
 0 1 0 1 2 

 i=0 j=1
 i=1 j=2
 i=2 j=3
 i=3 j=4
 i=4 j=0
 i=5 j=1
 i=6 j=2
 i=7 j=3
 i=8 j=4
 i=9 j=5
The pattern occurs at position 5

 i=10 j=3
 i=11 j=4
 i=12 j=5
The pattern occurs at position 8


Process completed.
*/